10976. Снова дроби?

Для заданного k (k > 0) найти все такие x, y (x ³ y), для которых

= +

Вход. Состоит из не более чем 100 тестов. Каждая строка содержит натуральное число k (k £ 10000).

Выход. Для каждого теста вывести количество пар (x, y), удовлетворяющих равенству. Вывести все найденные пары (x, y), как показано в примере, отсортировав значения x по убыванию.

Пример входа

2

12

Пример выхода

2

1/2 = 1/6 + 1/3

1/2 = 1/4 + 1/4

8

1/12 = 1/156 + 1/13

1/12 = 1/84 + 1/14

1/12 = 1/60 + 1/15

1/12 = 1/48 + 1/16

1/12 = 1/36 + 1/18

1/12 = 1/30 + 1/20

1/12 = 1/28 + 1/21

1/12 = 1/24 + 1/24

РЕШЕНИЕ

математика

Анализ алгоритма

Поскольку x ³ y, то £ . Откуда = + £ + = или 2k ³ y. Поскольку обе дроби и положительны, то > , откуда y > k или y ³ k + 1. Перебираем все возможные значения y (k + 1 £ y £ 2k), для каждого y находим соответствующее значение x из равенства = – . Получаем x = и проверяем, является ли x целым. Если x – целое, то выводим найденную пару (x, y).

Пример

Рассмотрим второй тест, где k =12. Перебираем 13 £ y £ 24. Каждому y соответствует x = , их значения приведены в таблице:

y	13	14	15	16	17	18	19	20	21	22	23	24
x	156	84	60	48	204/5	36	228/7	30	28	264/10	276/11	24

Все пары (x, y), для которых y целое, являются решениями исходного уравнения. Таких пар 8.

Реализация алгоритма

Поскольку сначала следует вывести число пар (x, y) – решений уравнения 1/k = 1/x + 1/y, а потом сами пары, то все найденные значения пар запоминаем в массивах _x и _y. Размер массивов равен MAX = 10001, поскольку k £ 10000. В переменной ptr храним количество найденных пар.

#define MAX 10001

int _x[MAX], _y[MAX], ptr;

Читаем входное значение k. Перебираем значения y, k + 1 £ y £ 2k. Для каждого y проверяем, делится ли k*y нацело на y – k. Если делится, то запоминаем найденную пару (x, y) в массивах.

while(scanf("%d",&k) == 1)

{

ptr = -1;

for(y = k + 1; y <= 2 * k; y++)

{

if (k * y % (y - k) == 0)

{

_x[++ptr] = k * y / (y - k);

_y[ptr] = y;

}

}

Выводим количество пар – решений. Выводим сами решения.

printf("%d\n",ptr+1);

for(i = 0; i <= ptr; i++)

printf("1/%d = 1/%d + 1/%d\n",k,_x[i],_y[i]);

}